\chapter{流密码(Stream Ciphers)}
流密码就是利用初始密钥产生一个密钥流，利用密钥流对数据流进行加密。密钥流和数据流，这个流是什么意思？\par

流（stream）从直观上来讲，应该是一种一个接着一个的运动方式。一个接着一个，这个“个”是什么？\par

“个”应该是一个最小单位，比如“人流”，这个“个”就是人，“水流”“泥石流”这个单位就不太好确定，与研究者的研究粒度和方法有关。\par
我们看看下面的一段文字(65个字符，包含标点符号)：\par

\begin{lstlisting}
  这是一门网络空间安全学科的基础课，是信息安全专业的一门专业基础课，
  学生通过学习这门课要理解加解密的基本原理，掌握基本的加解密方法。
\end{lstlisting}
\par

   这些文字存成纯文本模式（想想这个含义是什么？），有占195个字节(我的计算机是MacBook，我查看存储的txt文件，文件占用了4k的磁盘空间，想想为什么？)，简单计算可知一个字符占3个字节，用十六进制显示为：\par
   
\begin{lstlisting}
  E8BF99 E698AF E4B880 E997A8 E7BD91 E7BB9C E7A9BA E997B4 E5AE89 E585A8
  E5ADA6 E7A791 E79A84 E59FBA E7A180 E8AFBE EFBC8C E698AF E4BFA1 E681AF 
  E5AE89 E585A8 E4B893 E4B89A E79A84 E4B880 E997A8 E4B893 E4B89A E59FBA 
  E7A180 E8AFBE EFBC8C E5ADA6 E7949F E9809A E8BF87 E5ADA6 E4B9A0 E8BF99 
  E997A8 E8AFBE E8A681 E79086 E8A7A3 E58AA0 E8A7A3 E5AF86 E79A84 E59FBA 
  E69CAC E58E9F E79086 EFBC8C E68E8C E68FA1 E59FBA E69CAC E79A84 E58AA0 
  E8A7A3 E5AF86 E696B9 E6B395 E38082
\end{lstlisting}
\par
同样把这段信息以二进制编码的方式显示：\par
\begin{lstlisting}
00000000: 11101000 10111111 10011001 11100110 10011000 10101111  ......
00000006: 11100100 10111000 10000000 11101001 10010111 10101000  ......
0000000c: 11100111 10111101 10010001 11100111 10111011 10011100  ......
00000012: 11100111 10101001 10111010 11101001 10010111 10110100  ......
00000018: 11100101 10101110 10001001 11100101 10000101 10101000  ......
0000001e: 11100101 10101101 10100110 11100111 10100111 10010001  ......
00000024: 11100111 10011010 10000100 11100101 10011111 10111010  ......
0000002a: 11100111 10100001 10000000 11101000 10101111 10111110  ......
00000030: 11101111 10111100 10001100 11100110 10011000 10101111  ......
00000036: 11100100 10111111 10100001 11100110 10000001 10101111  ......
0000003c: 11100101 10101110 10001001 11100101 10000101 10101000  ......
00000042: 11100100 10111000 10010011 11100100 10111000 10011010  ......
00000048: 11100111 10011010 10000100 11100100 10111000 10000000  ......
0000004e: 11101001 10010111 10101000 11100100 10111000 10010011  ......
00000054: 11100100 10111000 10011010 11100101 10011111 10111010  ......
0000005a: 11100111 10100001 10000000 11101000 10101111 10111110  ......
00000060: 11101111 10111100 10001100 11100101 10101101 10100110  ......
00000066: 11100111 10010100 10011111 11101001 10000000 10011010  ......
0000006c: 11101000 10111111 10000111 11100101 10101101 10100110  ......
00000072: 11100100 10111001 10100000 11101000 10111111 10011001  ......
00000078: 11101001 10010111 10101000 11101000 10101111 10111110  ......
0000007e: 11101000 10100110 10000001 11100111 10010000 10000110  ......
00000084: 11101000 10100111 10100011 11100101 10001010 10100000  ......
0000008a: 11101000 10100111 10100011 11100101 10101111 10000110  ......
00000090: 11100111 10011010 10000100 11100101 10011111 10111010  ......
00000096: 11100110 10011100 10101100 11100101 10001110 10011111  ......
0000009c: 11100111 10010000 10000110 11101111 10111100 10001100  ......
000000a2: 11100110 10001110 10001100 11100110 10001111 10100001  ......
000000a8: 11100101 10011111 10111010 11100110 10011100 10101100  ......
000000ae: 11100111 10011010 10000100 11100101 10001010 10100000  ......
000000b4: 11101000 10100111 10100011 11100101 10101111 10000110  ......
000000ba: 11100110 10010110 10111001 11100110 10110011 10010101  ......
000000c0: 11100011 10000000 10000010 00001010                    ..
\end{lstlisting}
\par

对于怎么看上面的这一个数据流，其实与我们的处理方法，或者加密方法的是有关系的。通常我们将“流”看为一个二进制数据流。\par

\section{基本概念}
GF(2)是有两个元素的有限域，我们首先看看域中的加定义和乘定义。

GF(2)中的“加”运算也称为“异或”运算，通常用符号$\oplus$表示，其运算/函数定义见表\ref{tab:xor-def}：

\begin{table}[htbp]
	\centering
	\caption{"异或"运算/函数定义("异或"运算真值表)}
	\begin{tabular}{|c|c|c|}
		\hline
		x&y&$z=x\oplus y$\\
		\hline 
		0&0  &0  \\ 
		\hline 
		0&1  &1  \\ 
		\hline 
		1&0  &1  \\ 
		\hline 
		1& 1 & 0 \\ 
		\hline 
	\end{tabular} 
	\label{tab:xor-def}%
\end{table}

GF(2)中的“乘”运算也称为“与”运算，通常用符号$\wedge$表示，其运算/函数定义见表\ref{tab:and-def}：

\begin{table}[htbp]
	\centering
	\caption{"与"运算/函数定义("与"运算真值表)}
	\begin{tabular}{|c|c|c|}
		\hline
		x&y&$z=x\wedge y$\\
		\hline 
		0&0  &0  \\ 
		\hline 
		0&1  &0  \\ 
		\hline 
		1&0  &0  \\ 
		\hline 
		1& 1 & 1 \\ 
		\hline 
	\end{tabular} 
	\label{tab:and-def}%
\end{table}

在目前的数字计算机体系下，我们可以将信息看成一串二进制串流，也就是GF(2)的元素流。而对于加解密操作就是在其上的运算。\par


我们用小写$m,c,k\ldots$表示二进制的位,$m$表示原始数据，$c$表示加密后数据，$k$表示密钥，大写E表示二进制的运算（也可称为函数、算子），那么对于一个流加密我们可以表示为$c_i=E(m_i,k_i)$,其中$i=0,1,2,\ldots$,i表示是第几位。可以看到流密码的核心就是设计E和密钥流$k_0,k_1,k_2,\ldots$。但是由于是位运算，E也没有什么好设计的，我们只能采用异或运算，因为乘没有逆运算，异或运算还有一个优点，就是自己是自己逆运算，所以加解密都可以用这个运算。\par


那么流密码的设计将归结为密钥的设计，就是设计如何产生一个密钥流$k_i=G(s) \ ,i=0,1,2,\ldots$,其中s是产生密钥的种子(seeds)也叫初始密钥,也就是产生密钥流的一个初始值，G(generator)是密钥生成算法,并且产生的这个密钥流是别人无法预测的，或者不知道某个秘密的情况下是无法预测的。\par

流密码的加解密可以写为：\par
\[G(s)\oplus m_i =c_i \]
\[G(s)\oplus c_i =m_i  \]


\section{密钥的产生}

根据香浓的完全安全系统的定义，如果密钥流是一个随机数，这个系统就是一个完全安全加密系统，但是真正随机的要求，我们通常无法或很难达到，我们会用“接近”随机的数来代替，这个接近随机的数我们称为“伪随机数”，我们会设计伪随机数发生器PRG(pesudo-random generator )来产生密钥流。

\subsection{线性同余发生器LCG(linear congruential generator)}
可以利用$x_n=(ax_{n-1}+b) \ mod\ m$产生一个周期不超过m的伪随机数序列，$x_0$为种子(seed)，也就是密钥，这种方法称为线性同余发生器，缩写为LCG。\par


LCG不用在密码学中，因其在1977年被J.A.\ Reeds破译，也就是找到预测的方法，但是其在一些需要产生随机数的场合下依然有应用，比如在一些测试中。\par
下面我么实际给出一个例子，计算一下，使得大家有个直观感觉。\par

\vspace{1cm}
\begin{example}
	序列的同余递推式：
	\[x_n=2x_{n-1} \pmod{5}\]
	初始值$x_0=3$，产生的序列依次为：$x_1=1,x_2=2,x_3=4,x_4=3,x_5=1,x_6=2,x_7=4$，可见其产生的循环序列$(3,1,2,4)^*$.
\end{example}
\vspace{1cm}

我们看看另外一个例子，它的序列同余递推式为：
\[x_n=2x_{n-1}+3 \pmod{307}\]
	
我们在SageMath内编写一小段程序(见表\ref{LCD307-sagepro}),看看其所产生的序列。\par
\begin{table}[htbp]
	\centering
	\caption{同余方程$x_n=2x_{n-1}+3 \pmod{307}$输出序列的SageMath程序}
	\label{LCD307-sagepro}
	\begin{lstlisting}
	sage: b=67
	....: for i in range(0,307):
	....:     a=b
	....:     b=mod(2*a+3,307)
	....:     print i,":",b
	....:
	\end{lstlisting}
\end{table}

\setlength{\columnsep}{1cm}%调整两列中间的距离
\setlength{\columnseprule}{1pt} 
\def \columnseprulecolor{\color{blue}}%定义分割线的颜色
\begin{multicols}{4}
start\\
0 : 137\\
	1 : 277\\
	2 : 250\\
	3 : 196\\
	4 : 88\\
	5 : 179\\
	6 : 54\\
	7 : 111\\
	8 : 225\\
	9 : 146\\
	10 : 295\\
	11 : 286\\
	12 : 268\\
	13 : 232\\
	14 : 160\\
	15 : 16\\
	16 : 35\\
	17 : 73\\
	18 : 149\\
	19 : 301\\
	20 : 298\\
	21 : 292\\
	22 : 280\\
	23 : 256\\
	24 : 208\\
	25 : 112\\
	26 : 227\\
	27 : 150\\
	28 : 303\\
	29 : 302\\
	30 : 300\\
	31 : 296\\
	32 : 288\\
	33 : 272\\
	34 : 240\\
	35 : 176\\
	36 : 48\\
	37 : 99\\
	38 : 201\\
	39 : 98\\
	40 : 199\\
	41 : 94\\
	42 : 191\\
	43 : 78\\
	44 : 159\\
	45 : 14\\
	46 : 31\\
	47 : 65\\
	48 : 133\\
	49 : 269\\
	50 : 234\\
	51 : 164\\
	52 : 24\\
	53 : 51\\
	54 : 105\\
	55 : 213\\
	56 : 122\\
	57 : 247\\
	58 : 190\\
	59 : 76\\
	60 : 155\\
	61 : 6\\
	62 : 15\\
	63 : 33\\
	64 : 69\\
	65 : 141\\
	66 : 285\\
	67 : 266\\
	68 : 228\\
	69 : 152\\
	70 : 0\\
	71 : 3\\
	72 : 9\\
	73 : 21\\
	74 : 45\\
	75 : 93\\
	76 : 189\\
	77 : 74\\
	78 : 151\\
	79 : 305\\
	80 : 306\\
	81 : 1\\
	82 : 5\\
	83 : 13\\
	84 : 29\\
	85 : 61\\
	86 : 125\\
	87 : 253\\
	88 : 202\\
	89 : 100\\
	90 : 203\\
	91 : 102\\
	92 : 207\\
	93 : 110\\
	94 : 223\\
	95 : 142\\
	96 : 287\\
	97 : 270\\
	98 : 236\\
	99 : 168\\
	100 : 32\\
	101 : 67\\
	\colorbox{yellow}{********}\\
	102 : 137\\
	103 : 277\\
	104 : 250\\
	105 : 196\\
	106 : 88\\
	107 : 179\\
	108 : 54\\
	109 : 111\\
	110 : 225\\
	111 : 146\\
	112 : 295\\
	113 : 286\\
	114 : 268\\
	115 : 232\\
	116 : 160\\
	117 : 16\\
	118 : 35\\
	119 : 73\\
	120 : 149\\
	121 : 301\\
	122 : 298\\
	123 : 292\\
	124 : 280\\
	125 : 256\\
	126 : 208\\
	127 : 112\\
	128 : 227\\
	129 : 150\\
	130 : 303\\
	131 : 302\\
	132 : 300\\
	133 : 296\\
	134 : 288\\
	135 : 272\\
	136 : 240\\
	137 : 176\\
	138 : 48\\
	139 : 99\\
	140 : 201\\
	141 : 98\\
	142 : 199\\
	143 : 94\\
	144 : 191\\
	145 : 78\\
	146 : 159\\
	147 : 14\\
	148 : 31\\
	149 : 65\\
	150 : 133\\
	151 : 269\\
	152 : 234\\
	153 : 164\\
	154 : 24\\
	155 : 51\\
	156 : 105\\
	157 : 213\\
	158 : 122\\
	159 : 247\\
	160 : 190\\
	161 : 76\\
	162 : 155\\
	163 : 6\\
	164 : 15\\
	165 : 33\\
	166 : 69\\
	167 : 141\\
	168 : 285\\
	169 : 266\\
	170 : 228\\
	171 : 152\\
	172 : 0\\
	173 : 3\\
	174 : 9\\
	175 : 21\\
	176 : 45\\
	177 : 93\\
	178 : 189\\
	179 : 74\\
	180 : 151\\
	181 : 305\\
	182 : 306\\
	183 : 1\\
	184 : 5\\
	185 : 13\\
	186 : 29\\
	187 : 61\\
	188 : 125\\
	189 : 253\\
	190 : 202\\
	191 : 100\\
	192 : 203\\
	193 : 102\\
	194 : 207\\
	195 : 110\\
	196 : 223\\
	197 : 142\\
	198 : 287\\
	199 : 270\\
	200 : 236\\
	201 : 168\\
	202 : 32\\
	203 : 67\\
	204 : 137\\
	205 : 277\\
	206 : 250\\
	207 : 196\\
	208 : 88\\
	209 : 179\\
	210 : 54\\
	211 : 111\\
	212 : 225\\
	213 : 146\\
	214 : 295\\
	215 : 286\\
	216 : 268\\
	217 : 232\\
	218 : 160\\
	219 : 16\\
	220 : 35\\
	221 : 73\\
	222 : 149\\
	223 : 301\\
	224 : 298\\
	225 : 292\\
	226 : 280\\
	227 : 256\\
	228 : 208\\
	229 : 112\\
	230 : 227\\
	231 : 150\\
	232 : 303\\
	233 : 302\\
	234 : 300\\
	235 : 296\\
	236 : 288\\
	237 : 272\\
	238 : 240\\
	239 : 176\\
	240 : 48\\
	241 : 99\\
	242 : 201\\
	243 : 98\\
	244 : 199\\
	245 : 94\\
	246 : 191\\
	247 : 78\\
	248 : 159\\
	249 : 14\\
	250 : 31\\
	251 : 65\\
	252 : 133\\
	253 : 269\\
	254 : 234\\
	255 : 164\\
	256 : 24\\
	257 : 51\\
	258 : 105\\
	259 : 213\\
	260 : 122\\
	261 : 247\\
	262 : 190\\
	263 : 76\\
	264 : 155\\
	265 : 6\\
	266 : 15\\
	267 : 33\\
	268 : 69\\
	269 : 141\\
	270 : 285\\
	271 : 266\\
	272 : 228\\
	273 : 152\\
	274 : 0\\
	275 : 3\\
	276 : 9\\
	277 : 21\\
	278 : 45\\
	279 : 93\\
	280 : 189\\
	281 : 74\\
	282 : 151\\
	283 : 305\\
	284 : 306\\
	285 : 1\\
	286 : 5\\
	287 : 13\\
	288 : 29\\
	289 : 61\\
	290 : 125\\
	291 : 253\\
	292 : 202\\
	293 : 100\\
	294 : 203\\
	295 : 102\\
	296 : 207\\
	297 : 110\\
	298 : 223\\
	299 : 142\\
	300 : 287\\
	301 : 270\\
	302 : 236\\
	303 : 168\\
	304 : 32\\
	305 : 67\\
	306 : 137\\
\end{multicols}
\par

\begin{note}\cite{schneier-应用密码学}
	线性同余发生器的优点是：速度快，每位只需很少的运算。\par
	然而，线性同余发生器不能用在密码学中，因为它们是可预测的。线性同余发生器首
	先被 Jim Reeds于1977年破译(文章"Cracking Random Number Generator"),Joan Boyar(见文章"Inferring a sequence generated by a linear congruence")1982年也提出一个一般性破译方法,另外，Boyar还破译了二次同余发生器：
	\[ X_n=(aX_{n-1}^2+bX_{n-1} +c) \pmod{m} \]
	和三次同余发生器:
	\[X_n=(aX_{n-1}^3+bX_{n-1}^2 +cX_{n-1}+d) \pmod{m}\]
	另一些研究人员将 Boyar的成果扩展到了任意多项式同余发生器3N假短线性同余发生器和未知参数的截短线性同余发生器也被破译。上述证据表明:同余发生器在密码学中并不适用。\par
	然而线性同余发生器在非密码学应用中得到了使用,比如仿真,根据最合理的经验测试,它们是有效的,并具有很好的统计性能。关于线性同余发生器实现方面的重要信息可在P L'Ecuyer 1990年的文章"Random Numbers for Simulation"中找到。\par
	许多人考察了组合线性同余发生器,结果是它并没有增加安全性,但是它有更长的周期并在某些随机性测试方面具有更好的性能.
\end{note}


\subsection{线性反馈移位寄存器LSFR(Linear Feedback shift register)}

首先我们看看一个工程实践中的实际情况，就是利用线性反馈移位寄存器(Linear Feedback shift register，缩写为LFSR)可以产生一个无限长序列，我么这里通过举例了解一下LFSR。\par

LFSR用逻辑电路图来表示，如\ref{lfsr-register}：\par
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{LFSR-REG-EXAMPLE.png}
	\caption{LFSR的逻辑电路图表示}
	\label{lfsr-register}
\end{figure}

LFSR用图形化逻辑表示方法，如\ref{lfsr-fig-example}:\par
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.4\textwidth]{LFSR-EXAMPLE.jpg}
	\caption{LFSR的图形化表示}
	\label{lfsr-fig-example}
\end{figure}

下面我们看一个有三个寄存器的例子。\par
我们首先设计一个移位寄存器，反馈直接由最低位(或者说输出)到最高位。如图\ref{lfsr-3-1}所示,
寄存器初始值为101，输出序列变化过程如表\ref{LFSR101OUTPUT}所示，其中输出比特用波浪线标识出来。
我们可以看出输入序列为：$\underbrace{101}\underbrace{101}\underbrace{101}\ldots$，输出序列的周期为3.\par

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.4\textwidth]{LFSR-3-1.png}
	\caption{3个寄存器直接由输出反馈最高位}
	\label{lfsr-3-1}
\end{figure} 

\begin{table}[htbp]
	\centering
	\caption{初始值为101的直接反馈移位寄存器输出序列}
	\label{LFSR101OUTPUT}
	\begin{tabular}{ccccccccccccc}
		1&0&\uwave{1}\\
		1&1&\uwave{0}&1\\
		0&1&\uwave{1}&0&1\\
		1&0&\uwave{1}&1&0&1\\
		1&1&\uwave{0}&1&1&0&1\\
		0&1&\uwave{1}&0&1&1&0&1\\
		1&0&\uwave{1}&1&0&1&1&0&1\\
		1&1&\uwave{0}&1&1&0&1&1&0&1\\
		0&1&\uwave{1}&0&1&1&0&1&1&0&1\\
	\end{tabular}
\end{table}

下面我们同样是3个寄存器，但是采用不同的反馈方式，如图\ref{lfsr-3-15}所示，寄存器初始值依然为：101，输出序列如表\ref{LFSR101MSequence}所示，其中输出比特用波浪线标识出来，我们可以看到输出序列为：$\underbrace{1010011}$ $\underbrace{1010011}$ $\underbrace{1010011}$ $10\ldots$，周期为7。\par

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.4\textwidth]{LFSR-3-15.png}
	\caption{3个寄存器最大循环周期反馈方式}
	\label{lfsr-3-15}
\end{figure}

\begin{table}[htbp]
	\centering
	\caption{初始值为101的反馈移位寄存器输出的序列}
	\label{LFSR101MSequence}
	\begin{tabular}{ccccccccccccccccccccccccc}
		1&0&\uwave{1}\\ 
		0&1&\uwave{0}&1\\ 
		0&0&\uwave{1}&0&1\\ 
		1&0&\uwave{0}&1&0&1\\ 
		1&1&\uwave{0}&0&1&0&1\\ 
		1&1&\uwave{1}&0&0&1&0&1\\ 
		0&1&\uwave{1}&1&0&0&1&0&1\\ 
		1&0&\uwave{1}&1&1&0&0&1&0&1\\ 
		0&1&\uwave{0}&1&1&1&0&0&1&0&1\\ 
		0&0&\uwave{1}&0&1&1&1&0&0&1&0&1\\ 
		1&0&\uwave{0}&1&0&1&1&1&0&0&1&0&1\\ 
		1&1&\uwave{0}&0&1&0&1&1&1&0&0&1&0&1\\ 
		1&1&\uwave{1}&0&0&1&0&1&1&1&0&0&1&0&1\\ 
		0&1&\uwave{1}&1&0&0&1&0&1&1&1&0&0&1&0&1\\  
		1&0&\uwave{1}&1&1&0&0&1&0&1&1&1&0&0&1&0&1\\ 
		0&1&\uwave{0}&1&1&1&0&0&1&0&1&1&1&0&0&1&0&1\\ 
		0&0&\uwave{1}&0&1&1&1&0&0&1&0&1&1&1&0&0&1&0&1\\ 
		1&0&\uwave{0}&1&0&1&1&1&0&0&1&0&1&1&1&0&0&1&0&1\\ 
		1&1&\uwave{0}&0&1&0&1&1&1&0&0&1&0&1&1&1&0&0&1&0&1\\ 
		1&1&\uwave{1}&0&0&1&0&1&1&1&0&0&1&0&1&1&1&0&0&1&0&1\\ 
		0&1&\uwave{1}&1&0&0&1&0&1&1&1&0&0&1&0&1&1&1&0&0&1&0&1\\ 
		1&0&\uwave{1}&1&1&0&0&1&0&1&1&1&0&0&1&0&1&1&1&0&0&1&0&1\\ 
		0&1&\uwave{0}&1&1&1&0&0&1&0&1&1&1&0&0&1&0&1&1&1&0&0&1&0&1\\ 
	\end{tabular} 
\end{table}


通过上面的例子，我们可以看出同等数量的寄存器，不同的反馈方法，输出序列的周期不同，那么这就引出一个问题，如何能输出最长周期？最长周期是多少？


\subsubsection{有限域上的多项式}

在一个域$F$上，我们可以定义一个多项式交换环，记为$F[x]$，$F[x]$与整数环很类似，特别是有着相同的除计算方法。


有限域(finite field，称为伽罗瓦域，Galois field)通常记为GF，域GF(2)，表示集合为两个元素\{0,1\}，集合上的两个运算为“异或”(用符号表示为Xor，对应通常的域定义种的加，记为+)和“与”(用符号表示为and，对应通常域定义中的乘，记为$\cdot$)。我们看看GF(2)的多项式(polynomial)环，这个多项式的系数(coefficients)来自于GF(2)。\par

\vspace{1cm}
\begin{example}
	我们罗列几个GF(2)的多项式(polynomial)环上的元素：\\
	$x^{26}$\\
	$x^{12}+x^{10}+x^9+x^7+1$\\
	$x^4 + x^3 +x +1$\\
	$x^2+x+1$\\
	1\\
\end{example}

\vspace{1cm}

\begin{definition}{多项式的度}{fubi}
	一个多项式的最高次数，我们称为此多项式的度(degree)。多项式$f(x)$的度记为$deg(f(x))$，有时在不引起混淆的情况下，也记为$deg\ f(x)$。
\end{definition}

\vspace{1cm}

\begin{example}
	看看下面的多项式度是多少。\par
	1.$x^4 + x^3 +x +1$\par
	2.$x^2+x+1$\par
	解答：度分别为4和2.
\end{example}

\vspace{1cm}

下面我们通过示例给出多项式环的加和乘运算解释。

\vspace{1cm}
\begin{example}
	多项式的完整表达。\par
	$x^7+x^6+1 = 1\cdot x^7 + 1\cdot x^6 + 0\cdot x^5 + 0\cdot x^4 + 0\cdot x^3 + 0 \cdot x^2 + 0\cdot x^1+ 1\cdot x^0$\\
	这个多项式的完整表达的系数是可以唯一表示这个多项式的，写出以上多项式系数为：
	\[11000001\]
\end{example}
\vspace{1cm}
\begin{example}
	加/减(addition/subtraction)运算示例。\par
	$
	(x^4 + x^3 +x +1)+ (x^4+x^2+x) \\
	=(1\cdot x^4 + 1\cdot x^4) + (1 \cdot x^3+ 0 \cdot x^3) +(0 \cdot x^2 + 1\cdot x^2)+(1\cdot x +1\cdot x)+(1\cdot x^0 +0 \cdot x^0)\\
	=0\cdot x^4+1\cdot x^3 +1\cdot x^2+1
	$\par
	上面的加，也可以用系数序列直接表示：\\
	$\begin{array}{rl}
		&11011 \\
	   +&\underline{10110}\\
	    &01101 \Longrightarrow x^3+x^2+1
	\end{array}$
\end{example}
\vspace{1cm}
\begin{example}
	乘(multiplication)运算示例。\par
	$
	(x^2+x+1)(x+1)\\
	=x^3+x^2+x+x^2+x+1\\
	=x^3+1
	$\\
	上面的乘，也可以用系数序列直接表示：\\
	$\begin{array}{rrl}
	     &  &111 \\
	\times&  &\underline{011}\\
	     &  &111\\
	     &\underline{1} &\underline{11}\\
	     & 1 &001 \Longrightarrow x^3+1
	\end{array}$
\end{example}

\vspace{1cm}

在多项式环中，并没有“除”运算的定义，而是来自于多项式环的“除法性质”(Division property for polynomials),所以“除”运算其实是分解多项式的算法。\footnote{q表示 Quotient，r表示Remainder}

\begin{theorem}{多项式的除性质}{fubi}
	$[F,+,\cdot]$是一个域，为$F[x]$是域上的多项式环，$f(x)$和$g(x)$是$F[x]$的两个元素，并且$g(x)\neq \mathbb{0}$,那么在$F[x]$中存在唯一多项式$q(x)$和$r(x)$，有
	\[f(x)=g(x)\cdot q(x)+r(x),deg(r(x)) < deg(g(x))\]
\end{theorem}


\begin{example}
	除(division)运算示例。\par
	我们先根据除的基本定义来计算：$
	(x^4+x^3+x+1)/(x^2+1)\Rightarrow \\
	(x^4+x^3+x+1) xor [(x^2+1)\cdot \uuline{x^2}]=(x^4+x^3+x+1) xor (x^4+x^2) =x^3+x^2+x+1 \Rightarrow  \\
	(x^3+x^2+x+1) xor [(x^2+1) \cdot \uuline{x}]=(x^3+x^2+x+1) xor (x^3+x) =x^2+1\Rightarrow  \\
	(x^2+1) xor [(x^2+1) \cdot \uuline{1}] =0
	$\par
	商是$x^2+x+1$，余是0.\par
	我们把上面的计算过程可以写成长除式：\par
	\[
	\begin{array}{ccccccc}
	& & x^2 &+x  &+1   &  & \\
	\cline{3-7}
	\multicolumn{2}{r}{x^2+1 \surd}
	&x^4  &+x^3&     &+x&+1 \\
	& & x^4 &    &+x^2 &  &   \\
	\cline{3-5}
	& &     & x^3&+x^2 &+x&   \\
	& &     & x^3&     &+x&   \\
	\cline{4-6}
	& &     &    &x^2  &  &+1   \\
	& &     &    &x^2  &  &+1   \\
	\cline{5-7}
	& &     &    &     &  &0
	\end{array}
	\]
	
	\par
	我们可以把上面的写法简化一下，直接写系数，这样就变成了二级制序列的除法，运算结束后，再把二进制序列转换为多项式。\\
	$x^4+x^3+x+1$对应序列11011\\
	$x^2+1$对应序列101\\
	长除式：	\par
	\[
	\begin{array}{ccccccc}
	& &  &  & 1  & 1 &1 \\
	\cline{3-7}
	\multicolumn{2}{r}{101 \surd}
	&1  &1& 0 &1&1 \\
	& & 1 & 0 &1 &  &   \\
	\cline{3-5}
	& &     & 1&1 &1&   \\
	& &     & 1& 0 &1&   \\
	\cline{4-6}
	& &     &    &1  &0&1   \\
	& &     &    &1  &0  &1   \\
	\cline{5-7}
	& &     &    &     &  &0
	\end{array}
	\]
	\par
	
\end{example}

\vspace{0.5cm}
所以，“除”并非域上算子，而是一个计算$q(x)$和$r(x)$的算法。

\begin{definition}{多项式的阶(order)}{fubi}
	设$p(x)$是GF(2)上的多项式，且$p(0)\neq 0$，多项式$p(x)$的阶(order)是一个最小整数e,e满足$p(x)$能整除$x^e +1$。
	\footnote{The highest order power in a univariate polynomial is known as its order (or, more properly, its polynomial degree). For example, the polynomial$P(x)=a_nx^n+...+a_2x^2+a_1x+a_0 $ is of order n, denoted degP(x)=n. It is preferable to use the word "degree" for the highest exponent in a polynomial, since a completely different meaning is given to the word "order" in polynomials taken modulo some integer (where this meaning is the one used in the multiplicative order of a modulus). In particular, the order of a polynomial P(x) with P(0)!=0 is the smallest integer e for which P(x) divides $x^e+1$ (Lidl and Niederreiter 1994). For example, in the finite field GF(2), the order of $x^5+x^2+1$ is 31, since $\dfrac{x^{31}+1}{x^5+x^2+1}=1+x^2+x^4+x^5+x^6+x^8+x^9+x^{13}+x^{14}+x^{15}+x^{16}+x^{17}+x^{20}+x^{21}+x^{23}+x^{26} \pmod{2}$
	.From \url{https://mathworld.wolfram.com/PolynomialOrder.html}}
\end{definition}
\vspace{0.5cm}
\begin{example}
	多项式$x^2+x+1$，从小到大遍历$x^e+1,e=3,4,\ldots$，用定义判断，可知$x^2+x+1$阶为3，$\dfrac{x^3+1}{x^2+x+1} = 0$。
\end{example}
\vspace{0.5cm}
一个素多项式(prime polynomial)是指不能表示为两个多项式乘积的多项式.对于任何度n，最少存在一个素多项式$p(x)$，并且使用这个素多项式，可以构成一个有限域，我们记为GF($2^n$)，需要注意的是，GF($2^n$)和GF(2)表示的含义有很大不同，GF($2^n$)表示的是一个多项式有限域，有些教材为了明确是多项式域，有时候也记为$GF(2^n)[x]$,运算为模$p(x)$.或者说我们可以以$p(x)$为模，对多项式域形成一个划分，在整数域上有剩余系等概念。\par

\vspace{1cm}
\begin{example}
	示例GF($2^4$).\par
	$p(x)=x^4+x+1$是一个素多项式，我们用这个素多项式构造GF($2^4$).\\
	$x^0(mod\ p(x))=\textbf{1} (mod\ p(x))$,注意此处\textbf{1}的含义是指$\textbf{1}\cdot anyone = anyone$,是单位元\\
	$x^1(mod\ p(x))=x (mod\ p(x))$\\
	$x^2(mod\ p(x))=x^2 (mod\ p(x))$\\
	$x^3(mod\ p(x))=x^3 (mod\ p(x))$\\
	$x^4(mod\ p(x))=x^4 \ xor\ p(x)= x^4\ xor\ x^4+x+1 = x+1$\footnote{注意此处模的基本概念，模是余的概念，多少基本单元剩下的。}\\
	$x^5(mod\ p(x))=x \cdot x^4=x(x+1)=x^2+x (mod\ p(x))$\\
	$x^6(mod\ p(x))=x \cdot x^5=x(x^2+x)=x^3+x^2 (mod\ p(x))$\\
	$x^7(mod\ p(x))=x \cdot x^6=x(x^3+x^2)=x^4+x^3 (mod\ p(x))=(x^4+x^3) xor (x^4+x+1)=x^3+x+1$\\
	$x^8(mod\ p(x))=x \cdot x^7 =x(x^3+x+1) = x^4+x^2+x (mod\ p(x))=(x^4+x^2+x) xor (x^4+x+1)=x^2+1$\\
	$x^9(mod\ p(x))=x \cdot x^8 =x(x^2+1) =x^3+x (mod\ p(x))$\\
	$x^{10}(mod\ p(x))=x \cdot x^9 =x(x^3+x)=x^4+x^2(mod\ p(x))=(x^4+x^2) xor (x^4+x+1)=x^2+x+1$\\
	$x^{11}(mod\ p(x))=x \cdot x^{10} =x(x^2+x+1)=x^3+x^2+x(mod\ p(x))$\\
	$x^{12}(mod\ p(x))=x \cdot x^{11} = x(x^3+x^2+x)(mod\ p(x))=(x^4+x^3+x^2) xor (x^4+x+1)=x^3+x^2+x+1$\\
	$x^{13}(mod\ p(x))=x \cdot x^{12} = x(x^3+x^2+x+1)(mod\ p(x))=(x^4+x^3+x^2+x) xor (x^4+x+1)=x^3+x^2+1$\\
	$x^{14}(mod\ p(x))=x \cdot x^{13} =x (x^3+x^2+1)(mod\ p(x))=(x^4+x^3+x) xor (x^4+x+1)=x^3+1$\\
	$x^{15}(mod\ p(x))=x \cdot x^{14} =x(x^3+1)(mod\ p(x))=(x^4+x) xor (x^4+x+1)=\textbf{1}$\\
	$x^{16}(mod\ p(x))=x \cdot x^{15} =x(mod\ p(x))$
	\par
	通过以上运算形成集合
	\[\{\textbf{1},x,x^2,x^3,x+1,x^2+x,x^3+x^2,x^3+x+1,x^2+1,x^3+x,x^2+x+1,x^3+x^2+x,x^3+x^2+x+1,x^3+x^2+1,x^3+1\}\]
	共15个元素，也就是$2^4-1$个。
\end{example}
\vspace{1cm}

通常找一个素多项式是一个困难问题，通常都会查表。\par

“$f(x)$是一个n次多项式，$f(x)$为不可约之模2多项式，则$f(x)$必能除尽$1+x^{2^n-1}$;若对任何正整数$r<2^n-1$，$f(x)$不能除尽$1+x^r$，则称$f(x)$为n次“本原多项式”(primitive polynomial) ”.\cite{戚征1972伪随机序列} 所以素多项式是本原多项式的必要条件，但不充分，如果是充分必要条件，这两个概念就等价了。\par

我们看看Partow给出的一个本原多项式列表(这个表共给出n为32的，但是整个表太大，所以此处只拷贝了n=2$\sim$8的)\footnote{来自于Partow的网站\url{https://www.partow.net/programming/polynomials/index.html}}：\par
\begin{lstlisting}
x^2 + x^1 + 1
x^3 + x^1 + 1
x^3 + x^2 + 1
x^4 + x^1 + 1
x^4 + x^3 + 1
x^4 + x^3 + x^2 + x^1 + 1
x^5 + x^2 + 1
x^5 + x^3 + 1
x^5 + x^3 + x^2 + x^1 + 1
x^5 + x^4 + x^2 + x^1 + 1
x^5 + x^4 + x^3 + x^1 + 1
x^5 + x^4 + x^3 + x^2 + 1
x^6 + x^1 + 1
x^6 + x^3 + 1
x^6 + x^4 + x^2 + x^1 + 1
x^6 + x^4 + x^3 + x^1 + 1
x^6 + x^5 + 1
x^6 + x^5 + x^2 + x^1 + 1
x^6 + x^5 + x^3 + x^2 + 1
x^6 + x^5 + x^4 + x^1 + 1
x^6 + x^5 + x^4 + x^2 + 1
x^7 + x^1 + 1
x^7 + x^3 + 1
x^7 + x^3 + x^2 + x^1 + 1
x^7 + x^4 + 1
x^7 + x^4 + x^3 + x^2 + 1
x^7 + x^5 + x^2 + x^1 + 1
x^7 + x^5 + x^3 + x^1 + 1
x^7 + x^5 + x^4 + x^3 + 1
x^7 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^7 + x^6 + 1
x^7 + x^6 + x^3 + x^1 + 1
x^7 + x^6 + x^4 + x^1 + 1
x^7 + x^6 + x^4 + x^2 + 1
x^7 + x^6 + x^5 + x^2 + 1
x^7 + x^6 + x^5 + x^3 + x^2 + x^1 + 1
x^7 + x^6 + x^5 + x^4 + 1
x^7 + x^6 + x^5 + x^4 + x^2 + x^1 + 1
x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1
x^8 + x^4 + x^3 + x^1 + 1
x^8 + x^4 + x^3 + x^2 + 1
x^8 + x^5 + x^3 + x^1 + 1
x^8 + x^5 + x^3 + x^2 + 1
x^8 + x^5 + x^4 + x^3 + 1
x^8 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
x^8 + x^6 + x^3 + x^2 + 1
x^8 + x^6 + x^4 + x^3 + x^2 + x^1 + 1
x^8 + x^6 + x^5 + x^1 + 1
x^8 + x^6 + x^5 + x^2 + 1
x^8 + x^6 + x^5 + x^3 + 1
x^8 + x^6 + x^5 + x^4 + 1
x^8 + x^6 + x^5 + x^4 + x^2 + x^1 + 1
x^8 + x^6 + x^5 + x^4 + x^3 + x^1 + 1
x^8 + x^7 + x^2 + x^1 + 1
x^8 + x^7 + x^3 + x^1 + 1
x^8 + x^7 + x^3 + x^2 + 1
x^8 + x^7 + x^4 + x^3 + x^2 + x^1 + 1
x^8 + x^7 + x^5 + x^1 + 1
x^8 + x^7 + x^5 + x^3 + 1
x^8 + x^7 + x^5 + x^4 + 1
x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x^1 + 1
x^8 + x^7 + x^6 + x^3 + x^2 + x^1 + 1
x^8 + x^7 + x^6 + x^4 + x^2 + x^1 + 1
x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^2 + x^1 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^1 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
\end{lstlisting}


\subsubsection{生成函数(Generating Function)}

生成函数是研究序列的一种工具。\par

序列$\{a_0,a_1,\ldots\}$的普通生成函数定义为
\[G(x)=a_0+a_1x+a_2 x^2+\ldots\]


\begin{example}
	序列$a_n=
	\begin{pmatrix}
	k\\
	n
	\end{pmatrix}
	$,$n\leq k$,当 $n>k$时$a_n=0$ 的普通生成多项式为：
	\[G(x)=\sum_{n=0}^{k} \begin{pmatrix}
	k\\
	n
	\end{pmatrix}x=(1+x)^k \]\footnote{根据二项式定理可以获得这个结果。}
\end{example}

对于序列$\{a_n\}$和$\{b_n\}$，如何将序列的加定义为$c_i=a_i+b_i,i=0,1,2,\ldots$,乘定义为$c_i=\sum_{j=0}^{i}a_i b_{i-j}$，那么序列$\{c_n\}$的生成函数分别是序列$\{a_n\}$和$\{b_n\}$生成函数的乘和加。


对于LFSR，反馈给出了序列的递推关系，通过推导\footnote{Solomon W. Golomb的“Shift Register Sequences”一书中有推导过程。}我们有
\[G(x)=\frac{\sum_{i=1}^{r}c_i x^i (a_{-i}x^{-i}+\ldots+a_{-1}x^{-1})}{1-\sum_{i=1}^{r}c_ix^i}\]
其中$a_{-r},\ldots,a_{-1}$在Golomb一书中是指初始状态。

从上式中可以看出，$G(x)$取决于初始条件$\{a_{-r},\ldots,a_{-1}\}$和反馈系数$\{c_1,\ldots,c_r\}$，事实上，式子分母与初始条件也没关系。


\subsubsection{LFSR的多项式表示}

一个LFSR可以用一元多项式来表示,移位寄存器与多项式的对应一般对应关系如图\ref{lfsr-polynomial}所示，移位寄存器序列的递推关系为：
\[a_n=c_1a_{n-1}+c_2 a_{n-2}+ \ldots + c_n a_0\]
以上等式可以变换为：
\[a_n+c_1a_{n-1}+c_2 a_{n-2}+ \ldots + c_n a_0\]
如果我们引入延迟因子$x$，也就是$a_n x=a_{n-1},a_n x^2=a_{n-2}$，那么上式可以写成：
\[a_n(1+c_1 x+c_2 x^2+\ldots+c_n x^n)=0\]
我们可以看出反馈关系与多项式$1+c_1 x +c_{2}x^{2}+\ldots+c_{n-1}x^{n-1}+c_n x^n$，其中$c_i \in {0,1}$是一一对应的。\par
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{shift-register-Polynomial.png}
	\caption{n位移位寄存器对应一元多项式}
	\label{lfsr-polynomial}
\end{figure} 

如图\ref{lfsr-3-1}的三位循环移位寄存器，其对应的多项式可表示为:
\[x^3+1\]
如图\ref{lfsr-3-15}的三位移位寄存器，其对应的多项式可以表示为：
\[x^3+x^2+1\]
\par
查表或根据定义验证可知$x^3+x^2+1$是一个本原多项式。\par

图形化表示LFSR有两种方式，图\ref{lfsr-polynomial}是Fibonacci configuration(斐波那契配置)，也称为external configuration。还有一种方式是Galois configuration(伽罗瓦配置)，可称为internel configuration，Galois configuration更加适合软件实现。

本原多项式$x^4+x+1$对应的Fibonacci configuration和Galois configuration如图\ref{inter-exter}所示。
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.9\textwidth]{inter-exter.png}
	\caption{LFSR的两种配置}
	\label{inter-exter}
\end{figure} 

对于Galois configuration $x^0$对应反馈到第一个寄存器，最高位包含，中间的$x^i$是$FF_i$到$FF_{i+1}$的连接，系数1表示有连接，0表示没有。

我们假设寄存器初始状态为：0011，计算两种配置产生的序列，表\ref{tab:galoisconf}是Galois配置生成序列的过程，表\ref{tab:Fibonacciconf}是Fibonacciconf配置生成序列的过程。

我们发现两种配置虽然产生的序列一样，但是Galois configuration是与多项式表示一一对应的，而 Fibonacci configuration更利于理解。Galois configuration FF1寄存器抽头引出，产生的序列为：
\[ \underline{100110101111000} \]
Fibonacci configuration 从右边第一个寄存器引出，产生的序列为：
\[ 11000\underline{100110101111000}\]


\begin{table}[htbp]
	\centering
	\caption{Galois configuration产生序列}
	\begin{tabular}{|c|c|c|c|}
		\hline 
		寄存器状态($FF_1FF_2FF_3FF_4$)& $p(x)x$ & $p(x)x \mod{x^4+x+1}$ & 多项式对应序列 \\ 
		\hline 
		1100& $x+1$ &  &  \\ 
		\hline
		0110& $x^2+x$ & $x^2+x$ & 0110 \\ 
		\hline
		0011& $x^3+x^2$ & $x^3+x^2$ & 0011  \\ 
		\hline
		1101& $x^4+x^3$ & $x^3+x+1$ & 1101 \\ 
		\hline
		1010& $x^5+x^4$ & $x^2+1$ & 1010 \\ 
		\hline
		0101& $x^6+x^5$ & $\ldots$  &  \\ 
		\hline
		1110& $x^7+x^6$ &  &  \\ 
		\hline
		0111& $x^8+x^7$ &  &  \\ 
		\hline
		1111& $x^9+x^8$ &  &  \\ 
		\hline
		1101& $x^{10}+x^9$ &  &  \\ 
		\hline 
	\end{tabular} 
	\label{tab:galoisconf}%
\end{table}


\begin{table}[htbp]
	\centering
	\caption{Fibonacci configuration产生序列}
	\begin{tabular}{|c|}
		\hline 
		寄存器状态\\ 
		\hline 
		0011\\ 
		\hline 
		0001\\ 
		\hline 
		1000\\ 
		\hline 
		0100\\ 
		\hline 
		0010\\ 
		\hline 
		1001\\ 
		\hline 
		1100\\ 
		\hline 
		0110\\ 
		\hline 
		1011\\ 
		\hline 
		0101\\ 
		\hline 
		1010\\ 
		\hline 
		1101\\ 
		\hline 
		1110\\ 
		\hline 
		1111\\ 
		\hline 
		0111\\ 
		\hline
		0011\\ 
		\hline
		0001\\ 
		\hline
		1000\\ 
		\hline
		0100\\ 
		\hline
		0010\\ 
		\hline 
	\end{tabular} 
	\label{tab:Fibonacciconf}%
\end{table}

\vspace{1cm}
\begin{example}
	我们给定一个二进制序列1001011，其多项式表示为：
	\[1\cdot x^7+1\cdot x^6+0\cdot x^5 + 1\cdot x^4 +0\cdot x^3+0\cdot x^2+1\cdot x\]
	我们选择反馈函数为一个7阶本原多项式$x^7+x+1$，对上面的多项式乘x，变为：
	\[1\cdot x^8+1\cdot x^7+0\cdot x^6 + 1\cdot x^5 +0\cdot x^4+0\cdot x^3+1\cdot x^2 \mod{x^7+x+1}\]
	乘x相等于右移，右移后x的一次项系数由反馈函数决定。
\end{example}
\vspace{1cm}

设当前寄存器状态表示为一个多项式$p(x)=\sum_{i=0}^{r-1}a_ix^i$，反馈对应的本原多项式为$Q(x)$，那么下一个状态为$p(x)x \mod{Q(x)}$，这种计算方法与Galois LFSR配置方式的序列表现是一致的。

对于一个由n个寄存器组成的LFSR，其最多可能的状态是$2^n$个，但是在全零状态，其后续状态不会变化，所以我们除去这个状态，那也就是说n个寄存器组成的LFSR最多可能有$2^n-1$个状态。\par
\centerline{\textcolor{red}{\bfseries 我们希望在一定的资源配置下，能够得到周期最长的伪随机序列。}}
在二十世纪六十年代左右，人们对LFSR进行了系统的研究，国外对其系统研究的学者Golomb出版了一本书Shift Register Sequences\cite{10.5555/3153732}对移位寄存器的研究成果有系统的阐述，我国中科院数学研究所的戚征也在1972在"数学的实践与认识"期刊上发表了“伪随机序列”，肖国镇在1985年也出版“伪随机序列及其应用”\cite{肖国震1985伪随机序列及其应用}一书，书中也有系统的阐述。下面我们只看几个重要的结论，关于移位寄存器详细讨论可以参考相关文献。\par


\begin{theorem}{LFSR最大周期}{fubi}
	n级LFSR产生的序列最大周期为$2^n-1$.我们将最大周期序列，称为m序列。
\end{theorem}

\begin{theorem}{LFSR最大周期必要条件}{fubi}
	n级LFSR产生的序列最大周期$2^n-1$的必要条件是其特征多项式是不可约的。
\end{theorem}

\begin{definition}{本原多项式}{fubi}
	若n次不可约多项式p(x)的阶为$2^n-1$，则称p(x)为n次本原多项式。
\end{definition}

\begin{theorem}{m序列充要条件}{fubi}
	$\left\lbrace a_i\right\rbrace  \in G\left( p\left( x\right) \right) $,$\left\lbrace a_i\right\rbrace $为m序列的充要条件是$p\left( x\right) $是本原多项式。
\end{theorem}

当我们从移位寄存器的比特输出上考虑问题时，我们通常会采用生成方程(generating function)的研究方法，但是如果考虑整个移位寄存器状态时，我们会选用矩阵的方法(Matrix method)。

\subsubsection{LFSR的矩阵表示}

有时为了计算方便，我们也可以使用矩阵来表示LFSR的时间序列。\par
如果将n位LFSR在初始时刻的状态看为一个n维向量$\alpha_0 =[a_0\ a_1\ \ldots \ a_{n-1}]$，那么迁移到下一个时刻的状态向量$\alpha_1 =[a_1\ a_2\ \ldots \ a_{n}]$,根据LFSR反馈函数，我们知：
\[a_n=c_1 a_{n-1}+c_2 a_{n-2}+\ldots +c_n a_0\]
所以状态的迁移我们可以表示为：
\[\alpha_1 = \alpha_0 A\]
\[\begin{bmatrix} a_1& a_2 &\ldots &a_{n} \end{bmatrix}= 
  \begin{bmatrix} a_0& a_1 &\ldots &a_{n-1} \end{bmatrix}
	\begin{bmatrix}
	0 & 0 & \dots & 0 & c_{n}\\
	1 & 0 & \dots & 0 & c_{n-1}\\
	0 & 1 & \dots & 0 & c_{n-1}\\
	\ldots \\
	0 & 0 & \dots & 1 & c_{2}\\
	0 & 0 & \dots & 0 & c_{1}
	\end{bmatrix}
\]

\section{序列的伪随机性}
我们知道流密码的安全性取决于密钥流的“安全性”，密钥流的安全性就是指其不易被破解，也就是是有良好的随机性，那么什么是“好的随机性”？\par
我们先看几个基本概念，然后看看Golomb定义随机的。\par
我们先看看游程的概念，对于一个0、1序列$0100110001110101111$(长度19)，从左到右，依次有：\\
\begin{center}
	0的1游程\\
	1的1游程\\
	0的2游程\\
	1的2游程\\
	0的3游程\\
	1的3游程\\
	0的1游程\\
	1的1游程\\
	0的1游程\\
	1的4游程
\end{center}
\par
总结可知0的1游程3个，1的1游程2个，0的2游程1个，1的2游程1个，0的3游程1个，1的3游程1个，1的4游程1个，可以根据游程计算序列长度:
\[1\times 3+ 1\times 2 +2 \times 1+2 \times 1+3\times 1+3\times 1+4 \times 1=19\]
序列中0的个数:
\[1\times 3+2 \times 1+3\times 1=8 \]
序列中1的个数:
\[1\times 2+2 \times 1+3\times 1+4\times 1=11 \]
\par


\begin{definition}{序列的自相关函数(Autocorrelation Function)}{fubi}
	GF(2)上的周期为T的序列${a_i}$的自相关函数为
	\begin{equation}
		R(\tau) =  \frac{1}{T}\sum_{k=1}^{T}(-1)^{a_k}(-1)^{a_{k+\tau}},0\leq \tau \leq T-1
	\end{equation}
\end{definition}

我们知道:
\[(-1)^1 =-1,(-1)^0 =1\]
\[(-1)^1(-1)^1=1,(-1)^0(-1)^0=1,(-1)^1(-1)^0=-1\]

所以有$a_k=a_{k+\tau}$时,$(-1)^{a_k}(-1)^{a_{k+\tau}}=1$,$a_k\neq a_{k+\tau}$时,$(-1)^{a_k}(-1)^{a_{k+\tau}}=-1$。\par

易知$\tau=0$时，$R(0)=1$,下面我们看一个简单计算示例。

\vspace{1cm}
\begin{example}
	我们假设有一个周期为5的序列：01010，我们知道$R(0)=1$，下面计算$R(1)$,序列右移1位，与原序列关系为\\
	$\begin{array}{ccccccc}
		\text{原序列} & 0 & 1 & 0 & 1 & 0 & 0 \\ 
		\tau=1 &  & 0 & 1 & 0 & 1 & 0 \\ 
		\text{对比计算} &  & -1 & -1 & -1 & -1 & 1
	\end{array} $\\
	可得$R(1)=-\dfrac{3}{4}$。
\end{example}
\vspace{1cm}
Golomb提出了伪随机周期序列应该满足3个随机性公设\cite{yang-mcry}：
\begin{enumerate}
	\item 在序列的一个周期内，0与1的个数相差最多为1.
	\item 在序列的一个周期内，长为1的游程占游程总数的$\frac{1}{2}$，长为2的游程占游程总数的$\frac{1}{2^2}$，\ldots,长为i的游程占游程总数的$\frac{1}{2^i}$，\ldots，且在等长的游程中0的游程个数与1的游程个数相等。
	\item 自相关函数是0和一个常数。
\end{enumerate}
第一个公设说明序列${a_i}$中0和1出现的概论基本上相同，第二个公设说明0与1在序列中每一个位置上出现的概率相同，公设三表示，通过对序列与其平移后的序列进行比较，不能给出其他任何信息。\par

Golomb在"Shift register sequences"一书的Chaper III 4.RANDOMNESS PROPERTIES OF SHIFT REGISTER SEQUENCES中对移位寄存器序列满足这三个性质进行了证明。总结书中结论，其英文表述如图\ref{golomb-rand-postu-eng}所示。
\footnote{Golomb's Randomness postulates很多中文书翻译为Golomb随机性公设，在Bing的电子词典\url{https://cn.bing.com/dict}中postulate解释为：\\
1.
<formal>an idea that is an important part of a theory, argument, or explanation\\
2.
an unfounded or disputable unproved assumption\\
3.
a proposition or assumption taken to be self-evident or obvious\\
4.
a demand or request\\
公设的表述不是很贴切，因为通常公设是无需去证明的。
}\par

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{Golomb-rand-postulates.png}
	\caption{Golomb's Randomness postulates\footnote{图片来自\url{https://people.math.carleton.ca/~dthomson/Teaching/MATH5901-F13/pdfs/GeorgiosLFSR.pdf}}}
	\label{golomb-rand-postu-eng}
\end{figure}

从密码系统的角度看，伪随机序列还应满足以下条件\cite{yang-mcry}：
\begin{enumerate}
	\item ${a_i}$的周期相当大。
	\item ${a_i}$的确定在计算上时容易的。
	\item 由密文和相应的明文的部分信息，不能确定整个密钥序列${a_i}$。
\end{enumerate}

\begin{theorem}{m序列随机性定理}{fubi}
	GF(2)上的n长m序列${a_i}$，具有如下性质：\par
	(1)在一个周期内，0、1出现的次数分别为$2^{n-1}-1$和$2^{n-1}$.
	\par
	(2)在一个周期内，总游程数为$2^{n-1}$。对$1 \leq i \leq n-2$,长为i的游程有$2^{n-i-1}$个，且0、1游程各半。长为n-1的0游程一个，长为n的1游程一个.
	\par
	(3)${a_i}$的自相关函数为：
	\[ R(\tau)=\left\lbrace \begin{matrix}
	1,\tau =0\\
	-\dfrac{1}{2^n -1},0 < \tau \leq 2^n -2
	\end{matrix} \right.
	\]
	\par
\end{theorem}

\section{伪随机序列名称的由来\cite{戚征1972伪随机序列}}
在抛掷一枚均匀的硬币时,若出现正面记为l,出现背面记为-l,我们就得到一个随机的二元序列;当抛掷的次数足够多时,所得序列具有下列三条随机特性:\par
1)序列中1的个数与-1的个数接近相等。\par
2)把连在一起的1(或-l)称为“游程”,其中1(或 -1)的个数称为此游程的长度.列中长度为1的游程约占游程总数的1/2,长度为2的约占1/4
,长度为3的约占1/8,....在同长度的所有游程中,1的游程与-1的游程各占半数光景.\par
3)序列的x自相关函数的均值(期望值)在原点为最高，在离开原点时迅速下降。\par
以上是真正的二元随机序列的特性，通常所谓的“伪随机序列”是指具有此三条特性的一部或全部的二元序列。其所以加上个“伪”字，是因为这些序列尽管表面上满足随机特性，但实际上他们都是按一定规律形成的“确定性”序列。序列是否随机取决于其产生过程，仅由其最终形式是无法判定的。\par

在实际应用中，自相关函数的绝对值在原点之值应远远大于在其他点之值，才便于在相关检测时把它们区别开来，所以，自相关性3)在以下特别受到注意。

\section{m序列的破解}
我们看对于m序列的流加密，已知明文攻击的讨论。\par
假设我们已知密钥是n级LFSR生成的m序列，我们获得连续的$n+1$个长度的信息和对应的明文，我们可以根据密文$c_i$和明文$m_i$对计算密钥，我们知道$c_i=m_i \oplus k_i$,所以有$c_i \oplus m_i=(m_i \oplus k_i) \oplus m_i=k_i $，所以我们可以计算出$n+1$长的密钥序列，我们记为：
\[ a_h,a_{h+1},a_{h+2},\ldots,a_{h+n} \]
我们设密钥序列的特征方程系数分别为$c_n,c_{n-1},\ldots,c_1$，我们有递推式：
\[ a_{h+n}=c_n a_{h+n-1} + c_{n-1} a_{h+n-2} + \ldots+ c_1 a_h \]
用向量表示：
\[a_{h+n}=\begin{bmatrix} c_1& c_2 &\ldots &c_{n} \end{bmatrix}
\begin{bmatrix}
a_{h}\\
a_{h+1}\\
\ldots \\
a_{h+n-1}
\end{bmatrix}
 \]
假设我们还可以获取后面的n-1个密文和对应的明文信息，同理，我们可以计算其对应的密钥序列$a_{h+n+1},a_{h+n+2},\ldots,a_{h+2n-1}$,我们可以列出下式：
\[\begin{bmatrix} a_{h+n} \\ a_{h+n+1} \\ \ldots \\ a_{h+2n-1} \end{bmatrix}
=\begin{bmatrix} c_1& c_2 &\ldots &c_{n} \end{bmatrix}
\begin{bmatrix}
a_{h} & a_{h+1} & \dots & a_{h+n}\\
a_{h+1} & a_{h+2} & \dots & a_{h+n+1}\\
\ldots \\
a_{h+n-1}& a_{h+n} & \dots & a_{h+2n-1}
\end{bmatrix}
\]
我们记：
\[D=\begin{bmatrix}
a_{h} & a_{h+1} & \dots & a_{h+n}\\
a_{h+1} & a_{h+2} & \dots & a_{h+n+1}\\
\ldots \\
a_{h+n-1}& a_{h+n} & \dots & a_{h+2n-1}
\end{bmatrix}
\]
如果D存在逆，我们就可以根据我们获得的2n个数据求出特征方程系数，也就是破解此密码系统。我们可以证明D的存在\cite{yang-mcry}。关于有限域(Finite Field或Galois Field)上的布尔矩阵(BOOLEAN MATRICES)的逆的讨论\footnote{注意同一个东西，在发展过程中称谓的演变，这对于去查阅资料，尤其时原始资料时非常有用，比如这里的布尔矩阵，有时人们也会称为有限域的二值矩阵、Galois filed binary matrices、inver of matix over GF(2)等。}，可以参考D. E. Rutherford 在1962年的文章“INVERSES OF BOOLEAN MATRICES”。\par
求得特征方程后，我们就可以根据计算出来的密钥流得到后续的密钥序列，并且可以根据后续获取的密文序列计算出来明文。

\vspace{1cm}
\begin{example}
	假设对手获得流加密系统密文串“101101011110010”和对应的明文串"011001111111001"，并且知道密钥流使用的是5级线性反馈寄存器产生的，破解此加密系统。
\end{example}
\begin{solution}
	(1)利用已知明文和对应密文进行异或，获取密钥流:\\
	\begin{tabular}{cccccccccccccccc}
	cypher	& 1&0&1&1&0&1&0&1&1&1&1&0&0&1&0  \\ 
	plain	& 0&1&1&0&0&1&1&1&1&1&1&1&0&0&1  \\ 
	key	    & 1&1&0&1&0&0&1&0&0&0&0&1&0&1&1  \\ 
	note	& $a_1$&$a_2$&$a_3$&$a_4$&$a_5$&$a_6$&$a_7$&$a_8$&$a_9$&$a_{10}$&$a_{11}$&$a_{12}$&$a_{13}$&$a_{14}$&$a_{15}$  \\ 
	\end{tabular} 
	
	\par
	(2)因为是5级LFSR，所以我们只用连续取密钥流中10个bit就可以计算特征方程系数，罗列方程如下：
	\[
	\begin{bmatrix}
	a_6&a_7&a_8&a_9&a_{10}
	\end{bmatrix}=\begin{bmatrix}c_1&c_2&c_3&c_4&c_5\end{bmatrix}
	\begin{bmatrix}
	a_1&a_2&a_3&a_4&a_5\\
	a_2&a_3&a_4&a_5&a_6\\
	a_3&a_4&a_5&a_6&a_7\\
	a_4&a_5&a_6&a_7&a_8\\
	a_5&a_6&a_7&a_8&a_9\\
	\end{bmatrix}
	\]
	即：
	\[
	\begin{bmatrix}
	0&1&0&0&0
	\end{bmatrix}=\begin{bmatrix}c_1&c_2&c_3&c_4&c_5\end{bmatrix}
	\begin{bmatrix}
	1&1&0&1&0\\
	1&0&1&0&0\\
	0&1&0&0&1\\
	1&0&0&1&0\\
	0&0&1&0&0\\
	\end{bmatrix}
	\]
	那么：
	\[
	\begin{bmatrix}c_1&c_2&c_3&c_4&c_5\end{bmatrix}=\begin{bmatrix}	0&1&0&0&0 \end{bmatrix}
	\begin{bmatrix}
	1&1&0&1&0\\
	1&0&1&0&0\\
	0&1&0&0&1\\
	1&0&0&1&0\\
	0&0&1&0&0\\
	\end{bmatrix}^{-1}
	\]
	(3)下面我们求逆矩阵，这里面需要注意的是加和乘运算是定义在GF(2)上的，这里我们用Gauss-Jordan Elimination方法(通常翻译为“高斯-约旦消元法”，也有翻译为“高斯－若尔当消元法”、“高斯-约当消元法”\footnote{刚开始看到这个翻译，就有个疑问，Jordan为什么不翻译为“乔丹”，篮球明星不就是这么翻译的吗？而且通常名字翻译是音译，所以翻译为“乔丹”每毛病。后来查了以下，才知道，数学家Jordan，全名Jordan，Marie Ennemond Camille ( 1838～1922) ,是个法国人，一生都在法国，而Jordan的法语发音是“若尔当”,原来如此。顺便说一下问什么会在很多地方使用因为，这个用意是便于大家查阅，一是避免翻译上的不同造成的困扰，二是方便大家查阅原始文献。} )，计算过程如下：\\
	首先进行扩展：
	\[\left[ \begin{array}{ccccc:ccccc}
	1 & 1 & 0 & 1 & 0 &    1 & 0 & 0 & 0 & 0\\ 
	1 & 0 & 1 & 0 & 0 &    0 & 1 & 0 & 0 & 0\\
	0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
	1 & 0 & 0 & 1 & 0 &    0 & 0 & 0 & 1 & 0\\
	0 & 0 & 1 & 0 & 0 &    0 & 0 & 0 & 0 & 1\\
	\end{array}	\right] 
	\]
	因为GF(2)上元素只有0或1，所以我们只要选定对角线上元素不为零的，固定这个元素，只需进行行加(在此代数结构中就是异或)运算，就可以将固定下来的这个对角线元素所在列的其他元素全变为零，或者进行行对调，在后面的运算过程中，用$R_2 \leftrightarrow R_4$表示第二行和第四行互换，如果固定元素是(1,1)，那么我们用$R_1+R_3$表示将第一行和第三行相加，替换第三行，下面我们先进行行对调，调整以下矩阵,：
	\[\left[ \begin{array}{ccccc:ccccc}
	1 & 1 & 0 & 1 & 0 &    1 & 0 & 0 & 0 & 0\\ 
	1 & 0 & 1 & 0 & 0 &    0 & 1 & 0 & 0 & 0\\
	0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
	1 & 0 & 0 & 1 & 0 &    0 & 0 & 0 & 1 & 0\\
	0 & 0 & 1 & 0 & 0 &    0 & 0 & 0 & 0 & 1\\
	\end{array}	\right] \overset{R_2\leftrightarrow R_3\\}{\longrightarrow}
	\left[ \begin{array}{ccccc:ccccc}
	1 & 1 & 0 & 1 & 0 &    1 & 0 & 0 & 0 & 0\\ 
	0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
	1 & 0 & 1 & 0 & 0 &    0 & 1 & 0 & 0 & 0\\	
	1 & 0 & 0 & 1 & 0 &    0 & 0 & 0 & 1 & 0\\
	0 & 0 & 1 & 0 & 0 &    0 & 0 & 0 & 0 & 1\\
	\end{array}	\right] 
	\]
	\[\overset{R_2+ R_5 \rightarrow R_5\\}{\longrightarrow}
	\left[ \begin{array}{ccccc:ccccc}
	1 & 1 & 0 & 1 & 0 &    1 & 0 & 0 & 0 & 0\\ 
	0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
	1 & 0 & 1 & 0 & 0 &    0 & 1 & 0 & 0 & 0\\	
	1 & 0 & 0 & 1 & 0 &    0 & 0 & 0 & 1 & 0\\
	0 & 1 & 1 & 0 & 1 &    0 & 0 & 1 & 0 & 1\\
	\end{array}	\right]
	\]
	下面我们先固定(1,1),把同列变换为0：\\
	\[ \left[ \begin{array}{ccccc:ccccc}
		1 & 1 & 0 & 1 & 0 &    1 & 0 & 0 & 0 & 0\\ 
		0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
		1 & 0 & 1 & 0 & 0 &    0 & 1 & 0 & 0 & 0\\	
		1 & 0 & 0 & 1 & 0 &    0 & 0 & 0 & 1 & 0\\
		0 & 1 & 1 & 0 & 1 &    0 & 0 & 1 & 0 & 1\\
	\end{array}	\right] \overset{R_1+R_3 \\ R_1+R_4}{\longrightarrow}
	\left[ \begin{array}{ccccc:ccccc}
	1 & 1 & 0 & 1 & 0 &    1 & 0 & 0 & 0 & 0\\ 
	0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
	0 & 1 & 1 & 1 & 0 &    1 & 1 & 0 & 0 & 0\\	
	0 & 1 & 0 & 0 & 0 &    1 & 0 & 0 & 1 & 0\\
	0 & 1 & 1 & 0 & 1 &    0 & 0 & 1 & 0 & 1\\
	\end{array}	\right]
	\]
	
	固定(2,2),把同列变换为0:
	\[\left[ \begin{array}{ccccc:ccccc}
		1 & 1 & 0 & 1 & 0 &    1 & 0 & 0 & 0 & 0\\ 
		0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
		0 & 1 & 1 & 1 & 0 &    1 & 1 & 0 & 0 & 0\\	
		0 & 1 & 0 & 0 & 0 &    1 & 0 & 0 & 1 & 0\\
		0 & 0 & 1 & 0 & 0 &    0 & 0 & 0 & 0 & 1\\
	\end{array}	\right]\overset{R_2+R_1 \\ R_2+R_3 \\ R_2+R_4 \\ R_2+R_5}{\longrightarrow}
	\left[ \begin{array}{ccccc:ccccc}
	1 & 0 & 0 & 1 & 1 &    1 & 0 & 1 & 0 & 0\\ 
	0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
	0 & 0 & 1 & 1 & 1 &    1 & 1 & 1 & 0 & 0\\	
	0 & 0 & 0 & 0 & 1 &    1 & 0 & 1 & 1 & 0\\
	0 & 0 & 1 & 0 & 0 &    0 & 0 & 0 & 0 & 1\\
	\end{array}	\right]
	\]
	
	固定(3,3),把同列变换为0:
	\[\left[ \begin{array}{ccccc:ccccc}
		1 & 0 & 0 & 1 & 1 &    1 & 0 & 1 & 0 & 0\\ 
		0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
		0 & 0 & 1 & 1 & 1 &    1 & 1 & 1 & 0 & 0\\	
		0 & 0 & 0 & 0 & 1 &    1 & 0 & 1 & 1 & 0\\
		0 & 0 & 1 & 0 & 0 &    0 & 0 & 0 & 0 & 1\\
	\end{array}	\right]\overset{R_3+R_5}{\longrightarrow}
	\left[ \begin{array}{ccccc:ccccc}
	1 & 0 & 0 & 1 & 1 &    1 & 0 & 1 & 0 & 0\\ 
	0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
	0 & 0 & 1 & 1 & 1 &    1 & 1 & 1 & 0 & 0\\	
	0 & 0 & 0 & 0 & 1 &    1 & 0 & 1 & 1 & 0\\
	0 & 0 & 0 & 1 & 1 &    1 & 1 & 1 & 0 & 1\\
	\end{array}	\right] 
	\]
	\[\overset{R_4\leftrightarrow R_5}{\longrightarrow}
	\left[ \begin{array}{ccccc:ccccc}
	1 & 0 & 0 & 1 & 1 &    1 & 0 & 1 & 0 & 0\\ 
	0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
	0 & 0 & 1 & 1 & 1 &    1 & 1 & 1 & 0 & 0\\	
	0 & 0 & 0 & 1 & 1 &    1 & 1 & 1 & 0 & 1\\
	0 & 0 & 0 & 0 & 1 &    1 & 0 & 1 & 1 & 0\\
	\end{array}	\right]
	\]
	固定(4,4),把同列变换为0：
	\[\left[ \begin{array}{ccccc:ccccc}
		1 & 0 & 0 & 1 & 1 &    1 & 0 & 1 & 0 & 0\\ 
		0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
		0 & 0 & 1 & 1 & 1 &    1 & 1 & 1 & 0 & 0\\	
		0 & 0 & 0 & 1 & 1 &    1 & 1 & 1 & 0 & 1\\
		0 & 0 & 0 & 0 & 1 &    1 & 0 & 1 & 1 & 0\\
	\end{array}	\right] \overset{R_4+R_1\\R_4+R_3}{\longrightarrow}
	\left[ \begin{array}{ccccc:ccccc}
	1 & 0 & 0 & 0 & 0 &    0 & 1 & 0 & 0 & 1\\ 
	0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
	0 & 0 & 1 & 0 & 0 &    0 & 0 & 0 & 0 & 1\\	
	0 & 0 & 0 & 1 & 1 &    1 & 1 & 1 & 0 & 1\\
	0 & 0 & 0 & 0 & 1 &    1 & 0 & 1 & 1 & 0\\
	\end{array}	\right] 
	\]
	固定(5,5),把同列变换为0：
	\[\left[ \begin{array}{ccccc:ccccc}
		1 & 0 & 0 & 0 & 0 &    0 & 1 & 0 & 0 & 1\\ 
		0 & 1 & 0 & 0 & 1 &    0 & 0 & 1 & 0 & 0\\
		0 & 0 & 1 & 0 & 0 &    0 & 0 & 0 & 0 & 1\\	
		0 & 0 & 0 & 1 & 1 &    1 & 1 & 1 & 0 & 1\\
		0 & 0 & 0 & 0 & 1 &    1 & 0 & 1 & 1 & 0\\
	\end{array}	\right] \overset{R_5+R_2\\R_5+R_4}{\longrightarrow}
	\left[ \begin{array}{ccccc:ccccc}
	1 & 0 & 0 & 0 & 0 &    0 & 1 & 0 & 0 & 1\\ 
	0 & 1 & 0 & 0 & 0 &    1 & 0 & 0 & 1 & 0\\
	0 & 0 & 1 & 0 & 0 &    0 & 0 & 0 & 0 & 1\\	
	0 & 0 & 0 & 1 & 0 &    0 & 1 & 0 & 1 & 1\\
	0 & 0 & 0 & 0 & 1 &    1 & 0 & 1 & 1 & 0\\
	\end{array}	\right]
	\]
	
	现在我们知道：\\
	\[
	\begin{bmatrix}
	1&1&0&1&0\\
	1&0&1&0&0\\
	0&1&0&0&1\\
	1&0&0&1&0\\
	0&0&1&0&0\\
	\end{bmatrix}^{-1}=\begin{bmatrix}
	0 & 1 & 0 & 0 & 1 \\
	1 & 0 & 0 & 1 & 0 \\
	0 & 0 & 0 & 0 & 1 \\
	0 & 1 & 0 & 1 & 1 \\
	1 & 0 & 1 & 1 & 0 \\
	\end{bmatrix}
	\]
	(4)计算特征方程系数：
	\[
	\begin{bmatrix}c_1&c_2&c_3&c_4&c_5\end{bmatrix}=\begin{bmatrix}	0&1&0&0&0 \end{bmatrix}
	\begin{bmatrix}
	0 & 1 & 0 & 0 & 1 \\
	1 & 0 & 0 & 1 & 0 \\
	0 & 0 & 0 & 0 & 1 \\
	0 & 1 & 0 & 1 & 1 \\
	1 & 0 & 1 & 1 & 0 \\
	\end{bmatrix}=\begin{bmatrix}1&0&0&1&0\end{bmatrix}
	\]
	\par
\end{solution}
\vspace{1cm}

通常在解决实际问题时，比如在CTF竞赛时，我们可以使用Sagemath求解GF(2)域上矩阵的逆，上面例题中Sagemath\footnote{SageMath is a free open-source mathematics software system licensed under the GPL. It builds on top of many existing open-source packages: NumPy, SciPy, matplotlib, Sympy, Maxima, GAP, FLINT, R and many more. Access their combined power through a common, Python-based language or directly via interfaces or wrappers.Mission: Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab.官网地址\url{https://www.sagemath.org/index.html}.\\
Sagemath创建人是William Stein(个人网页\url{https://wstein.org/idx_personal.html},他是华盛顿大学的一个数学副教授，其为了教学方便开始集成Python的数学包，形成Sage)}求解代码如下：\\
\begin{lstlisting}
	a = matrix(GF(2),5,5)
	a[0]=[1,1,0,1,0]
	a[1]=[1,0,1,0,0]
	a[2]=[0,1,0,0,1]
	a[3]=[1,0,0,1,0]
	a[4]=[0,0,1,0,0]
	a.is_invertible()
	b = matrix(GF(2),5,5)
	b=a.inverse()
	b
	c= matrix(GF(2),1,5)
	c[0]=[0,1,0,0,0]
	c*b
\end{lstlisting}
输出结果为：\\
\begin{lstlisting}
	True
	0  1  0  0  1 
	1  0  0  1  0 
	0  0  0  0  1 
	0  1  0  1  1 
	1  0  1  1  0 
	
	[1 0 0 1 0]
\end{lstlisting}

\section{非线性序列}
为了使得密钥流\underline{更加随机}(这样的说法其实是不严谨的，什么是更加随机？序列符合随机性定义？前面讨论过LFSR已经满足了，那么更加随机是什么？\footnote{此处更加随机应该是指周期更长})，可使用多个LFSR来构造序列生成器，这多个LFSR的输出可以做为一个非线性组合函数的输入，新的序列生成器产生的序列周期应该尽可能大，但是从理论上可以证明新序列的周期不会大于各LFSR周期的乘积。
\subsection{Geff发生器}
三个LFSR产生的输出分别为$a^1,a^2,a^3$，在t时刻的输出记为$a_t^1,a_t^2,a_t^3$，Geff的t时刻输出为$b_t = (a_t^1\wedge a_t^2)\oplus (\neg a_t^1 \wedge a_t^3)$.

\section{RC4}


RC4是Rivest在1987年发明的，是Rivest Cipher 4的缩写。\par

RC4在密钥流产生中利用了分组密码S盒的思想，下面是一段关于RC4的英文介绍，读者可以通过这段介绍对RC4有一个大致了解。\par

\bigskip
\centerline{*************************扩展阅读*************************}
\bigskip
RC4 is an encryption algorithm that was created by Ronald Rivest of RSA Security. It is used
in WEP and WPA, which are encryption protocols commonly used on wireless routers. The
workings of RC4 used to be a secret, but its code was leaked onto the internet in 1994. RC4 was
originally very widely used due to its simplicity and speed. Typically 16 byte keys are used for
strong encryption, but shorter key lengths are also widely used due to export restrictions. Over
time this code was shown to produce biased outputs towards certain sequences, mostly in first
few bytes of the keystream generated. This led to a future version of the RC4 code that is more
widely used today, called RC4-drop[n], in which the first n bytes of the keystream are dropped in
order to get rid of this biased output. Some notable uses of RC4 are implemented in Microsoft
Excel, Adobe's Acrobat 2.0 (1994), and BitTorrent clients.\footnote{本段文字来自于\url{https://sites.math.washington.edu/~nichifor/310_2008_Spring/Pres_RC4Encryption.pdf}}
\par
\bigskip
\centerline{**************************************************}
\bigskip



\section{流密码的应用}
流密码有很多实际应用，比如用于DVD(Digital Videodisk)的加密CSS(content scramble system)，有广泛用于汽车的PKE(Passive Keyless entry)，大家注意，并不是所有PKE使用的都是流加密，PKE有些方案使用的分组加密。\par

RC4(Rivest Cipher 4的缩写)也是一个流密码，但这个流的最小单位(基本单位)是字节，RC4算法采用$mod\ 256$运算产生一个伪随机字节流，然后与明文异或。"RC4已经成为一些常用的协议和标准的一部分，如1997年的WEP和2003/2004年无线卡的WPA,1995年的SSL，以及后来1999年的TLS。让它如此广泛分布和使用的主要因素是它不可思议的简单和速度，不管是软件还是硬件，实现起来都十分容易。但是研究者发现存在部分弱密钥，使得子密钥序列在不到100万字节内就发生了完全的重复，如果是部分重复，则可能在不到10万字节内就能发生重复，因此，推荐在使用RC4算法时，必须对加密密钥进行测试，判断其是否为弱密钥。目前发现的主要问题是在无线网络中IV（初始化向量）不变性漏洞。\footnote{https://baike.baidu.com/item/RC4}"